import java.util.Arrays;


public class SegmentTree {
	
	
	public static void main(String[] args) {
		int[] a = new int[] {3, 4, 1};
		int[] segTree = constructSegmentTree(a);
		System.out.println(Arrays.toString(segTree));
		System.out.println(query(segTree, 1, 2, a.length));
		update(a, segTree, 2, 0);
		System.out.println(Arrays.toString(segTree));
		System.out.println(query(segTree, 1, 2, a.length));
		
	}
	
	public static void update(int[] a, int[] segTree, int index, int update) {
		a[index] = update;
		updateSegTree(segTree, 0, 0, a.length - 1, index, update);
	}
	
	public static void updateSegTree(int[] segTree, int rootNode, int start, int end, int index, int update) {
		if(start == end) {
			segTree[rootNode] = update;
			updateRoot(segTree, (rootNode - 1) / 2);
			return;
		}
		
		int mid = (start + end) / 2;
		if(start <= index && mid >= index) {
			updateSegTree(segTree, (rootNode * 2) + 1, start, mid, index, update);
		} else {
			updateSegTree(segTree, (rootNode * 2) + 2, mid + 1, end, index, update);
		}
	}
	
	public static void updateRoot(int[] segTree, int rootNode) {
		if(rootNode == 0) {
			segTree[rootNode] = Math.min(segTree[(rootNode * 2) + 1], segTree[(rootNode * 2) + 2]);
			return;
		}
		segTree[rootNode] = Math.min(segTree[(rootNode * 2) + 1], segTree[(rootNode * 2) + 2]);
		updateRoot(segTree, (rootNode - 1) / 2);
	}
	
	
	public static int query(int[] segTree, int startRange, int endRange, int arraySize) {
		return query(segTree, 0, startRange, endRange, 0, arraySize - 1);
	}
	
	public static int query(int[] segTree, int rootNodeIndex, int startRange, int endRange, int start, int end) {
		if(startRange > end || endRange < start) {
			return -1;
		}
		if(startRange <= start && endRange >= end) {
			return segTree[rootNodeIndex];
		}
		
		int leftResult = query(segTree, (rootNodeIndex * 2 + 1), startRange, endRange, start, (start + end) / 2);
		int rightresult = query(segTree, (rootNodeIndex * 2 + 2), startRange, endRange, ((start + end) / 2) + 1, end);
		if(leftResult == -1) {
			return rightresult;
		}
		if(rightresult == -1) {
			return leftResult;
		}
		return Math.min(leftResult, rightresult);
	}
	
	
	public static int[] constructSegmentTree(int[] a) {
		int[] segTree = new int[(a.length * 2) - 1];
		constrcutSegmentTree(a, segTree, 0, 0, a.length - 1);
		return segTree;
	}
	
	public static void constrcutSegmentTree(int[] a, int[] segTree, int rootNodeIndex, int start, int end) {
		if(start == end) {
			segTree[rootNodeIndex] = a[start];
			return;
		}
		
		constrcutSegmentTree(a, segTree, (rootNodeIndex * 2) + 1, start, (start + end) / 2);
		constrcutSegmentTree(a, segTree, (rootNodeIndex * 2) + 2, ((start + end) / 2) + 1, end);
		
		segTree[rootNodeIndex] = Math.min(segTree[(rootNodeIndex * 2 + 1)], segTree[(rootNodeIndex * 2 + 2)]);
		
	}

}
